import java.util.ArrayDeque;
import java.util.Deque;

public class RemoveDuplicates {
    /*
    * 删除字符串中的所有相邻重复项
    * 给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
    * 在 S 上反复执行重复项删除操作，直到无法继续删除。
    * 在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
    *
    * 1 <= S.length <= 20000
    * S 仅由小写英文字母组成。
    * */
    public static void main(String[] args){
        RemoveDuplicates removeDuplicates = new RemoveDuplicates();
        System.out.println(removeDuplicates.mySolution("aaa"));
    }

    // 我的想法：入栈，每个元素入栈前和栈顶比较，相等就弹栈
    public String mySolution(String s){
        if(s.length() == 1)
            return s;
        StringBuilder sBuilder = new StringBuilder(s.length());
        for (int i = 0; i < s.length(); i++) {
            if(sBuilder.length() == 0)
                sBuilder.append(s.charAt(i));
            else {
                char c = sBuilder.charAt(sBuilder.length()-1);
                if(c == s.charAt(i))    // 弹栈
                    sBuilder.deleteCharAt(sBuilder.length()-1);
                else    // 入栈
                    sBuilder.append(s.charAt(i));
            }
        }
        return sBuilder.toString();
    }
}
